# the calculation method comes from https://people.ece.ubc.ca/irenek/techpaps/introip/manual04.html
levels: list = [
	[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
	[[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
	[[0, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]],
	[[0, 1, 0, 1], [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]],
	[[0, 1, 0, 1], [1, 1, 1, 1], [0, 1, 0, 1], [1, 1, 1, 1]],
	[[0, 1, 0, 1], [0, 1, 1, 1], [0, 1, 0, 1], [1, 1, 1, 1]],
	[[0, 1, 0, 1], [0, 1, 1, 1], [0, 1, 0, 1], [1, 1, 0, 1]],
	[[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [1, 1, 0, 1]],
	[[0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]],
	[[0, 0, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1]],
	[[0, 0, 0, 1], [0, 1, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]],
	[[0, 0, 0, 0], [0, 1, 0, 1], [0, 1, 0, 0], [0, 1, 0, 1]],
	[[0, 0, 0, 0], [0, 1, 0, 1], [0, 0, 0, 0], [0, 1, 0, 1]],
	[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 1]],
	[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 0]],
	[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0]],
	[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
]

def pattern(img: list):
	"""
	:param img: the greyscale image array
	:return: halftone image through pattern
	"""
	# prepare the generated img
	out_img: list = []
	
	# find proper interval
	MIN: int = img.min()
	MAX: int = img.max()
	interval: int = (MAX - MIN) // 16
	
	# return 4x4 pattern dots according to pixel
	def find_pattern(pix: int):
		return levels[16 - ((pix - MIN) // interval)]
	
	# split img into pixels
	# and apply pattern to each pixel
	for row in img:
		row_pattern: list = [[], [], [], []]
		for pix in row:
			pattern = find_pattern(pix)
			row_pattern[0].extend(pattern[0])
			row_pattern[1].extend(pattern[1])
			row_pattern[2].extend(pattern[2])
			row_pattern[3].extend(pattern[3])
		out_img.append(row_pattern[0])
		out_img.append(row_pattern[1])
		out_img.append(row_pattern[2])
		out_img.append(row_pattern[3])
	
	# make each pixsel multiply 255
	return [[pix * 255 for pix in row] for row in out_img]

